package leetcode.editor.cn;

import java.util.*;
import leetcode.editor.common.*;

public class ThreeSum {

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public List<List<Integer>> threeSum(int[] nums) {
            Arrays.sort(nums);
            // n 为 3，从 nums[0] 开始计算和为 0 的三元组
            return nSumTarget(nums, 3, 0, 0);
        }

        // 注意：调用这个函数之前一定要先给 nums 排序
        // n 填写想求的是几数之和，start 从哪个索引开始计算（一般填 0），target 填想凑出的目标和
        private List<List<Integer>> nSumTarget(int[] nums, int n, int start, long target) {
            int sz = nums.length;
            List<List<Integer>> res = new ArrayList<>();
            // 至少是 2Sum，且数组大小不应该小于 n
            if (n < 2 || sz < n) return res;
            // 2Sum 是 base case
            if (n == 2) {
                // 双指针那一套操作
                int lo = start, hi = sz - 1;
                while (lo < hi) {
                    int sum = nums[lo] + nums[hi];
                    int left = nums[lo], right = nums[hi];
                    if (sum < target) {
                        while (lo < hi && nums[lo] == left) lo++;
                    } else if (sum > target) {
                        while (lo < hi && nums[hi] == right) hi--;
                    } else {
                        res.add(new ArrayList<>(Arrays.asList(left, right)));
                        while (lo < hi && nums[lo] == left) lo++;
                        while (lo < hi && nums[hi] == right) hi--;
                    }
                }
            } else {
                // n > 2 时，递归计算 (n-1)Sum 的结果
                for (int i = start; i < sz; i++) {
                    List<List<Integer>> sub = nSumTarget(nums, n - 1, i + 1, target - nums[i]);
                    for (List<Integer> arr : sub) {
                        // (n-1)Sum 加上 nums[i] 就是 nSum
                        arr.add(nums[i]);
                        res.add(arr);
                    }
                    // 相同的数字跳过，避免重复
                    while (i < sz - 1 && nums[i] == nums[i + 1]) i++;
                }
            }
            return res;
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)

    
    public static void main(String[] args) {
        Solution solution = new ThreeSum().new Solution();
        // put your test code here
        
    }
}
